//头结点
class LinkedNodeHead {
	constructor() {
		this.head = null
	}
}
//尾结点
class TailNode {
	constructor() {
		this.tail = null
	}
}
// 普通节点
class LinkedNode {
	constructor(element) {
		this.element = element
		this.next = null
		this.pre = null
	}
}
// 双向链表
class DoubleLinkedList {
	constructor() {
		this.head = new LinkedNodeHead() // 初始化头节点
		this.tail = new TailNode() // 初始化尾节点
		this.length = 0
	}
	// 向尾部添加一元素
	append(element) {
		const newNode = new LinkedNode(element)
		if (this.length === 0) {
			this.head = newNode
			this.tail = newNode
		} else {
			// 第一种写法-->以newNode为出发点  每一次的重现指向都有两种出发点
			newNode.pre = this.tail
			this.tail.next = newNode
			this.tail = newNode
			// 第二种写法-->以tail为出发点
			// this.tail.next = newNode
			// newNode.pre = this.tail
			// this.tail = newNode
		}
		this.length += 1
	}
	// 根据指定位置添加元素 true/false
	insert(position, element) {
		const newNode = new LinkedNode(element)
		if (position > this.length || position < 0) return false
		// 头插入
		if (position === 0) {
			this.head.pre = newNode
			newNode.next = this.head
			this.head = newNode
		} else if (position < this.length) {
			//中间插入
			let cur = this.head
			let pre = null
			let i = 0
			while (i++ < position) {
				pre = cur
				cur = cur.next
			}
			newNode.pre = pre
			pre.next = newNode
			newNode.next = cur
			cur.pre = newNode
		} else {
			// 尾部插入
			this.append(element)
			this.length -= 1 // append 已经加 1了
		}
		this.length += 1
		return true
	}
	// 根据位置获取元素  element
	get(postion) {
		if (postion >= this.length || postion < 0) return null
		const cur = this.getCurByPostion(postion)
		return cur.element
	}
	// 查找元素所在位置 -1 / position
	indexOf(element) {
		let cur = this.head
		let i = 0
		while (cur) {
			if (cur.element === element) {
				break
			}
			i += 1
			cur = cur.next
		}
		return i === this.length ? -1 : i
	}
	// 根据指定位置更新元素 true/false
	update(position, element) {
		if (position >= this.length || position < 0) return false
		const cur = this.getCurByPostion(position)
		cur.element = element
		return true
	}
	//根据指定位置移除元素 null/element
	removeAt(position) {
		if (position >= this.length || position < 0) return null
		let cur = this.head
		if (this.length === 1) {
			this.head = null
			this.tail = null
		} else {
			if (position === 0) {
				cur = this.head
				this.head = cur.next
				this.head.pre = cur
				return cur.element
			} else if (position == this.length - 1) {
				cur = this.tail
				this.tail = cur.pre
				this.tail.next = null
			} else {
				let i = 0
				cur = this.head
				let pre = null
				while (i < position) {
					pre = cur
					cur = cur.next
					i++
				}
				pre.next = cur.next
				cur.next.pre = pre
			}
		}
		this.length -= 1
		return cur.element
	}
	// 移除元素  null / element
	remove(element) {
		const position = this.indexOf(element)
		if (position !== -1) {
			return this.removeAt(position)
		} else {
			return null
		}
	}
	// 销毁链表
	destroy() {
		this.head = null
		this.tail = null
		this.length = 0
	}
	// 空链表
	isEmpty() {
		return this.length === 0
	}
	// 链表大小
	size() {
		return this.length
	}
	// 打印输出
	toString() {
		return this.forwardString()
	}
	// 正向遍历
	forwardString() {
		let cur = this.head
		let strList = []
		while (cur) {
			strList.push(cur.element)
			cur = cur.next
		}
		return strList.join(' ==> ')
	}
	// 反向遍历
	reverseString() {
		let cur = this.tail
		let strList = []
		while (cur) {
			strList.push(cur.element)
			cur = cur.pre
		}
		return strList.join(' ==> ')
	}
	// 方法抽取
	getCurByPostion(position) {
		let cur = this.head
		let i = 0
		// 算法优化
		if (position <= Math.floor(this.length / 2)) {
			// 从前向后遍历
			cur = this.head
			while (i++ < position) {
				cur = cur.next
			}
		} else {
			// 从后向前遍历
			i = this.length - 1
			cur = this.tail
			while (i-- < position) {
				cur = cur.pre
			}
		}
		return cur
	}
}
